package com.code.leetcode.offer;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/30 12:09
 */
public class The14_2_MX {
    public int cuttingRope(int num) {
        if (num <= 3) return num - 1;
        int m = num %  3;
        int p = 1000000007;
        long rem = 1, x = 3;
        for (int i = num / 3 - 1; i > 0; i /= 2) {
            if (i % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(m == 0) return (int)(rem * 3 % p);
        if(m == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }


    /**
     * 贪心
     */


    public static void main(String[] args) {
        The14_2_MX the14 = new The14_2_MX();
    }
}
